package com.david.learning.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class NewCard21 {
	private Object[] cards = new Object[] { 1, 2, 3, 4, 5, 6, 7, 8 };
	private Stack<Object> stack = new Stack<Object>();
	private List<Object> sequencies = new ArrayList<Object>();
	private iCalculator[] calculators = Card21.CALCULATORS;
	private Stack<Object> options = new Stack<Object>();
	private int goal = 9237;

	public static void main(String[] args) {
		NewCard21 instance = new NewCard21();
		instance.getSequence(instance.cards, 0, instance.cards.length);
		int sum = 0;
		for (Object o : instance.sequencies) {
			Object[] sequence = (Object[]) o;
			sum += instance.calculate(sequence, 0, 1);
		}
		System.out.println("sum = " + sum);
	}

	public int calculate(Object[] sequence, int begin, int result) {
		int sum = 0;
		if (begin == sequence.length) {
			if (result == this.goal) {
				printFormula(sequence, options, result);
				return 1;
			} else {
				return 0;
			}
		}
		if (begin == 0) {
			sum += calculate(sequence, begin + 1, ((Integer) sequence[begin]).intValue());
		} else {
			for (iCalculator c : calculators) {
				options.push(c);
				sum += calculate(sequence, begin + 1, c.calculate(result, ((Integer) sequence[begin]).intValue()));
				options.pop();
			}
		}
		return sum;
	}

	private void printFormula(Object[] sequence, Stack<Object> options, int result) {
		assert sequence != null && sequence.length > 1;
		assert options != null && options.size() > 1;
		assert sequence.length - 1 == options.size();
		System.out.print(sequence[0]);
		for (int i = 1; i < sequence.length; i++) {
			System.out.print(options.elementAt(i - 1) + " " + sequence[i]);
		}
		System.out.println(" = " + result);
	}

	public void getSequence(Object[] arr, int begin, int num) {
		if (num == 0) {
			sequencies.add(stack.toArray());
		} else {
			for (int i = begin; i < arr.length; i++) {
				stack.push(arr[i]);
				swap(arr, begin, i);
				getSequence(arr, begin + 1, num - 1);
				swap(arr, begin, i);
				stack.pop();
			}
		}
	}

	public void swap(Object[] arr, int from, int to) {
		if (from == to)
			return;
		Object tmp = arr[to];
		arr[to] = arr[from];
		arr[from] = tmp;
	}
}
